package code.jzh.compiler.scanner;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

import code.jzh.compiler.util.Constants;

public class DFA {
	public static int idGenerator = 1;
	public DFAState start;
	
	public Set<DFAState> dfaStates = new HashSet<DFAState>();
	
	public static DFA buildDFA(NFA nfa) {
		DFA dfa = new DFA();
		Set<DFAState> dest = new HashSet<DFAState>();
		Set<NFAState> nfaStart = new HashSet<NFAState>();
		nfaStart.add(nfa.start);
		Set<NFAState> nfaSet = nfa.epsilonClosure(nfaStart);
		
		DFAState dfaStateStart = new DFAState(idGenerator++, nfaSet);
		dfaStateStart.started = true;
		dfa.start = dfaStateStart;
		dest.add(dfaStateStart);
		Queue<DFAState> queue = new LinkedList<DFAState>();
		queue.add(dfaStateStart);
		
		while(!queue.isEmpty()) {
			DFAState curDFAState = queue.poll();
			for(char c : Constants.charList) {
				Set<NFAState> nfaStates = nfa.epsilonClosure(nfa.deltaCharClosure(curDFAState.nfaStates, c));
				if(nfaStates==null || nfaStates.size()==0)
					continue;
				DFAState dfaState = getDFAStateByNFAStates(nfaStates, dest);
				if(dfaState==null) {
					dfaState = new DFAState(idGenerator++, nfaStates);
					queue.add(dfaState);
					dest.add(dfaState);
				}
				curDFAState.addEdge(c, dfaState.id);
			}
		}
		dfa.dfaStates = dest;
		return dfa;
	}
	
	public static DFAState getDFAStateByNFAStates(Set<NFAState> nfaStates, Set<DFAState> dfaStates) {
		for(DFAState dfaState : dfaStates) {
			if(dfaState.equal(new DFAState(nfaStates)))
				return dfaState;
		}
		return null;
	}
	
	public DFAState getDFAStateById(int id) {
		for(DFAState state : dfaStates)
			if(state.id == id)
				return state;
		return null;
	}
	
	public void printDFA() {
		for(DFAState dfaState : dfaStates) {
			System.out.println("DFA STATE: "+dfaState.id
					+(dfaState.accepted?"\taccepted!!!":"")
					+(dfaState.started?"\tstarted!!!":""));
			for(char c : dfaState.edges.keySet()) {
				System.out.println("\t"+dfaState.id+"->"+c+"->"+dfaState.edges.get(c));
			}
		}
	}
}